package exclusiveor;

import org.junit.jupiter.api.Test;

import java.text.NumberFormat;

/**
 * 题目1：要求将一个二进制数最右侧的1保留，其余的位置补0输出。
 * 题目2：给定一个数，要求给出这个数的二进制位上总共有多少个1。
 * 题目3：如果数组中又两组数出现了奇数次，其他数都出现了偶数次，如何找到这两个出现了奇数次的数？
 */
public class XORFindData02 {

    /**
     * 给定一个数，要求给出这个数的二进制位上总共有多少个1。
     * 假设num为5，二进制表示为：0110
     * int num1 = num & ((~num) + 1)：0010  提取出来一个1，计数器加1
     * num = num ^ num1：0110 ^ 0010 = 0100 去除已经统计过的那个1，下一次循环统计剩下的1
     */
    private static int binary1Count(int num) {
        int count = 0; // 计数器
        while (num != 0) {
            int num1 = num & ((~num) + 1); // 0010，提取最右侧的那个1
            count++;
            num = num ^ num1; // 0100，去除已经统计过的那个1，下一次循环统计剩下的1
        }

        return count;
    }

    /**
     * 一个二进制数取反，就是将对应位置上的1改成0，0改成1的到的就是取反的结果，加1就是将原数的最右侧的1还原回去，
     * 再将本身和取反加1之后的二进制数进行与运算(与运算就是相同为1，相反为0)，那么得到的就是结果。
     * 所以核心算法公式为：n & (~n + 1)
     * 比如：0100取反： -取反-> 1011
     * 取反的数加1：  1011 -+1-> 1100,加1就是将原数的最右侧的1还原回去。
     * 原数和取反后数加1的数与运算： 0100 & 1100 --> 0100
     */
    private static int inversionSaveRight1(int a) { // 假如: a=4=0b0100
        int b = a & (~a + 1); // b=4=0b0100
        return Integer.parseInt(Integer.toBinaryString(b));
    }

    /**
     * 将一个数组中的所有数据都异或起来，那么得到的结果就是要找的那组数（XORFindData01中有证明），
     * 根据这理论，题目2中所有的数组中的数据异或起来，结果就是那两组出现了奇数次的数，再将结果与原数据
     * 进行与运算，得到的结果便是那两组出现了奇数次的数中某一个。
     * 例如：arr = {1,2,2,2,3,2};
     */
    public static void outOddNumber2(int[] arr) {
        int eor = XORFindData01.outOddNumber1(arr);
        int right1 = inversionSaveRight1(eor);
        int eor1 = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & right1) != 0) {
                eor1 = eor & arr[i]; // eor1 = 1 或者 3
            }
        }

        System.out.println(eor1); // eor1 = 1 或者 3
        System.out.println(eor1 ^ eor); // eor1 ^ eor = 1 ^ 3 ^ 1 = 3 或者 eor1 ^ eor = 1 ^ 3 ^ 3 = 1
    }

    @Test
    public void client() {

        /**
         * 题目1：核心算法公式为：n & (~n + 1)
         */
        NumberFormat instance = NumberFormat.getInstance();
        instance.setGroupingUsed(false);
        instance.setMinimumIntegerDigits(32); // 这里只是做了补位处理
        int right1 = inversionSaveRight1(4);
        System.out.println(instance.format(Integer.parseInt(String.valueOf(right1))));

        /**
         * 题目2：
         */
        int num = 2;
        int count = binary1Count(num);
        System.out.println(num + "的二进制表示为：" + Integer.toBinaryString(num) + ",二进制位上总共有：" + count + "个1.");

        /**
         * 题目3：
         */
        int[] arr = new int[]{1, 2, 2, 4, 8, 3, 3, 3, 3, 2, 1, 4, 4, 4};
        outOddNumber2(arr);
    }
}
